For any arbitrary pairing of source and destination across a computer network, whether the destination is reachable from the source depends on the states of the routing and filtering functional elements present in the network.
A routing functional element (herein generically referred to as a ‘router’) connects two or more logical subnets and serves to forward a packet received on one subnet to a destination on another subnet according to a locally-stored mapping between the packet final destination and the appropriate next subnet destination. The locally stored mapping (or ‘route’) is held in a routing table or routing information base, RIB (hereinafter, ‘RIB’ will be used generically to refer to the locally-stored mapping). The routes held in the RIB generally deal in groups of final destination addresses typically corresponding to one or more subnets. Where more than one route exists to a particular destination, the routes are generally given a preference weighting. If a destination is not in the RIB the router is unable to forward a packet intended for that destination. The RIB initially contains preset ‘static’ routes giving mappings to certain destinations; however, a router is also able to learn additional routes from its neighboring routers, this being achieved using one or more so-called ‘routing protocols’. A routing protocol enables a router to advertise its routes to neighboring routers (subject to any policy restrictions) thereby enabling the latter to extend its own RIB. Routing protocols can be divided into two main types, namely:                Exterior Gateway Protocols, EGP, for exchanging routing information between routers in different autonomous systems, AS; an example is the BGP ('Border Gateway Protocol') which in practice is the predominant EGP.        Interior Gateway Protocols, IGP, for exchanging routing information between routers in the same routing domain (an AS may have one or several routing domains); an example is the OSPF ('Open Shortest Path First') protocol.        
The operation of these routing protocols to extend the routes known to a router means that the contents of the router RIBs change dynamically whereby the fact that, at a particular point in time, a particular destination is not accessible from a particular source due to lack of routing information by one or more router, is no guarantee that the destination will remain unreachable.
A filtering functional element (herein generically referred to as a ‘filter’) serves to block/allow packets according to a set of rules typically expressed in terms of parameters such as the source/destination and/or the service specified in the packet (as used herein, ‘service’ means the combination of protocol and port number). A filter can be arranged to maintain context about active sessions (‘state information’). In this case, if a packet does not match an existing connection, it will be evaluated according to a ruleset for new connections; however, if the packet matches an existing connection, it will be allowed to pass without further processing. This feature is sometimes referred to as “keep state”.
From the foregoing description of routers and filters, it will be appreciated that there may be none, one or more paths through a network between a given pairing of source and destination for a given service and this may vary dynamically.
It should be noted that real-world devices embodying routing and filtering functionally (for example, switches and firewalls) may not necessarily be ‘pure’ in the sense of only incorporating one such functionality and not the other. For example, a switch may block certain services being sent out on a particular interface; in the present specification, such devices are considered as being a combination of the appropriate discrete routing and filtering functional elements. Where real-world devices are being referred to below, this will be stated explicitly; unqualified reference to a ‘router’ or ‘filter’ is, as already indicated, a reference to the corresponding functional element.
An example arrangement of routers and filters in a network is shown in FIG. 1 of the accompanying drawings. FIG. 1 shows a common network configuration for a managed service provider to provide data center space and management services for an enterprise customer with duplicate sites A and B (to provide redundancy and disaster recovery capabilities) interconnected on the customer side by primary and backup fiber links L1, L2. For each site, the network is broken into three parts—the customer compartment 10A/10B, an access compartment 11A/11B, which is shared between multiple customers, and a management and monitoring compartment 12A/12B (the compartments being interconnected by a VLAN L3).
For each site, the core of the customer installation 10A/10B is a pair of real-world layer-3 switches 13A/13B in a failover configuration. The switches 13A/13B are connected to the management and monitoring infrastructure of the service provider via a pair of real-world firewalls 14A/14B in an active/passive failover configuration.
Further real-world switches 16A/16B, 17A/17B, and 18A/18B are present in the customer access and management & monitoring compartments 11A/11B and 12A/12B. Further real-world firewalls 19A/19B are present in the customer access compartment 11A/11B.
Even in the relatively limited network of FIG. 1, errors in configuring the routers and filters can produce major problems and be difficult to track down. An example problem scenario for the FIG. 1 network is:                monitoring traffic from management host 200 is received at customer server 201 but response messages are not received back;        investigation shows that the monitoring traffic is reaching customer server 201 only via customer site B and the customer link L1 (that is, the traffic is coming via compartments 12B, 11B& 10B and not via 12A & 11A);        investigation also shows that the response messages from customer server 201 sent to switches 13A are being blocked at firewalls 14A.        it is found that the reason why the monitoring traffic from management host 200 reaches customer server 201 via customer site B is because the host 200 sends all its monitoring traffic through compartment 12B & 11B even if intended for customer site A;        the reason that the response messages are being blocked at the firewalls 14A is that these firewalls have the “keep state” feature and only allow through responses in respect of connections of which they already have a record—as the monitoring traffic for customer server 201 does not pass via the firewalls 14A, they have no record of a connection relevant to the response messages and so drop them.        
The long-term solution to this asymmetric forward-return path problem is to have the monitoring traffic for site A sent via compartments 12A and 11A. However, for operational reasons, the quickest and most convenient way to implement a short term fix may well be to re-configure the customer server 200 to send its responses via customer site B rather than to re-configure the management host 200 that monitors multiple customer sites.
In a large enterprise network that is managed by geographically distributed teams of operations engineers, problems such as the above that result from mis-configuration of routers and filters can take anything from hours to weeks to diagnose and fix. Moreover, with hundreds or thousands of routers and filters, the potential interactions between configurations are numerous and the cost of manually determining all end-to-end flows is prohibitive.
It is therefore highly desirable to provide an efficient and reliable way of confirming that the routers and filters of a network are correctly configured to satisfy a set of end-to-end requirements (where an end-to-end access requirement is one specifying, for a given source-destination pair, which packet types must flow through and which must be denied).
Formally, an end-to-end access requirement is represented as:                <source, destination, service, permission, prioriy>where source and destination correspond to sets of IP_addresses, service contains the source and destination ports, and protocol, permission is either “allow” or “deny,” and priority is a unique rank assigned to the requirement. A set of requirements is thus rank-ordered.        
As already indicated, the routing information in the router RIBs is likely to provide for multiple paths between a source-destination pair. Now, certain packet types (specified by port and protocol) between the source and destination may be blocked by filter rules along some (or all) of these paths. For any packet, there are three outcomes: (i) all paths from source to destination are blocked, (ii) no path is blocked, or (iii) some paths are blocked while others are not.
However, an end-to-end access requirement implies that either every possible path must allow the packet to go through, or else no path must allow the packet to go through. In other words, satisfying an end-to-end requirement means that the third option (some paths permit the packet while others block it) must be ruled out even in the face of the dynamic nature of the routing information stored in the router RIBs. This type of deterministic behavior in networks is critical to the long term security and stability of the environment.
Experimentally determining whether a set of end-to-end requirements is met is not a practical proposition not only due to the scale of the task in any large network, but also because of the dynamic nature of the router RIBs.
As the configuration data (comprising filter rules, router connectivity and route advertisement policies) is generally readily available, it would be convenient to be able to determine from this data whether a given set of end-to-end access requirements is satisfied taking into account all potential paths from a source to a destination, over all possible states of the network RIBs.
The paper “On static reachability analysis of IP networks” (Geoffrey G. Xie, Jibin Zhan, David A. Maltz, Hui Zhang, Albert G. Greenberg, Gisli Hjálmýsson, and Jennifer Rexford. INFOCOM, pages 2170-2183. IEEE, 2005 describes an abstract framework to study the static reachability problem. The framework is based on the use of dynamic programming to compute all possible accesses, aggregated over all possible states.